#include <iostream>

using std::cout;
using std::endl;

int sort(int *arr, int i, int j)
{
    int val = arr[i];
    while(i < j){
        while(i < j && arr[j] > val)
            j--;
        if(i < j)
            arr[i++] = arr[j];
        while(i < j && arr[i] < val)
            i++;
        if(i < j)
            arr[j--] = arr[i];
    }
    arr[i] = val;
    return i;
}

void topK(int *arr, int i, int j, int k)
{
    int pos = sort(arr, i, j);
    // 如果当前排序的索引要取的个数减一，说明前top个都找到了, 直接返回
    if(pos == k - 1) return;
    else if(pos < k - 1){
        topK(arr, pos + 1, j, k);
    }else{
        topK(arr, i, pos - 1, k);
    }
}

int getK(int *arr, int i, int j, int len, int k)
{
    int pos = sort(arr, i, j); 
    if(len - pos == k) return arr[pos];
    else if(k > len - pos){
        return getK(arr, i, pos - 1, len, k);
    }else{
        return getK(arr, pos + 1, j, len, k);
    }
}

int main(int args, char *argv[])
{
    int arr[] = {7, 3, 9, 1, 0, 4, 3, 8, 11, 13};
    int len = sizeof(arr) / sizeof(int);
    topK(arr, 0, len - 1, 7);
    for(int i{}; i < len; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
    cout << getK(arr, 0, len - 1, len, 3) << endl;
    return 0;
}